import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Stack;
import java.util.TreeMap;


public class Ex4_5 {


	public Ex4_5() {}

	public static void main(String[] args) {

		Ex4_5 exe = new Ex4_5();
		TreeMap<Integer,ArrayList<Integer>> edges = 
				exe.getGraph("C:\\Users\\josemfer\\Downloads\\dataset_57_2.txt");
		
		//Start with an empty stack and an empty circuit (eulerian path).
		// If all vertices have same out-degrees as in-degrees - choose any of them.
		// If all but 2 vertices have same out-degree as in-degree, and one of those 2 vertices has out-degree 
		//    with one greater than its in-degree, and the other has in-degree with one greater than its out-degree - 
		//    then choose the vertex that has its out-degree with one greater than its in-degree.
		//2. If current vertex has no out-going edges (i.e. neighbors) - add it to circuit, remove the last vertex from the stack and set it as the current one.
		//Otherwise (in case it has out-going edges, i.e. neighbors) - add the vertex to the stack, 
		//take any of its neighbors, remove the edge between that vertex and selected neighbor, and set that neighbor as the current vertex.
		//3. Repeat step 2 until the current vertex has no more out-going edges (neighbors) and the stack is empty.
	
		ArrayList<Integer> eulerPath = new ArrayList<Integer>();
		Stack<Integer> stack = new Stack<Integer>();		
		Integer current = exe.selectStartNode(edges);
		current = 0;
		ArrayList<Integer> outgoings = edges.get(current);
		
		do {								
			//remove the last vertex from the stack and set it as the current one
			if (outgoings == null || outgoings.size() == 0) {			
				eulerPath.add(current);
				current = stack.pop();
			} else { 
				// add the vertex to the stack
				stack.push(current);
				//take any of its neighbors
				Integer outgoing = outgoings.get(0);
				// remove the edge between that vertex and selected neighbor
				if (outgoings.size() == 1) {
					edges.remove(current);
				} else {
					outgoings.remove(0);
				}
				//set that neighbor as the current vertex
				current = outgoing;			
			}	
			outgoings = edges.get(current);			
		} while(!stack.isEmpty() ||  outgoings != null);
		
		eulerPath.add(current);
		Collections.reverse(eulerPath);
		for (Integer node : eulerPath) {
			System.out.print(node + "->");
		}
	}


	private Integer selectStartNode(TreeMap<Integer,ArrayList<Integer>> edges) {
		
		HashMap<Integer,Integer> inDegrees = new HashMap<Integer,Integer>();
		
		for (Entry<Integer,ArrayList<Integer>> edge : edges.entrySet()) {			
			ArrayList<Integer> outgoings = (ArrayList<Integer>) edge.getValue();
			for (Integer outgoing : outgoings) {
				if (inDegrees.containsKey(outgoing)) {
					Integer actualDegree = inDegrees.get(outgoing);
					 inDegrees.put(outgoing, actualDegree + 1);					
				} else {
					 inDegrees.put(outgoing, 1);		
				}
			}
		}
		
		for (Entry<Integer,ArrayList<Integer>> edge : edges.entrySet()) {			
			Integer origin = edge.getKey();
			ArrayList<Integer> outgoings = edge.getValue();
			Integer inDegree = inDegrees.get(origin);
			if (inDegree == null) {
				inDegree = 0;
			}
			Integer outDegree = outgoings.size();
			if (outDegree == inDegree + 1) {
				return origin;
			}			
		}	
		
		return null;
	}
	
	private TreeMap<Integer,ArrayList<Integer>> getGraph(String file) {		
		TreeMap<Integer,ArrayList<Integer>> cycle = new TreeMap<Integer,ArrayList<Integer>>();	
		try {
			BufferedReader br = new BufferedReader(new FileReader(file));
			String line;		
			while ((line = br.readLine()) != null) {
				line = line.trim();
				String[] split = line.split("->");
				String origin = split[0].trim();
				String dest[] = split[1].split(",");
				ArrayList<Integer> list = new ArrayList<Integer>();
				for (String d : dest) {
					list.add(Integer.valueOf(d.trim()));
				}		
				cycle.put(Integer.valueOf(origin), list);				
			}			
			br.close();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}		
		return cycle;
	}

}
